package SudokuAlex;

	import java.awt.Color;
	import java.awt.event.ActionEvent;
	import java.awt.event.KeyEvent;
	import java.awt.event.KeyListener;

	import javax.swing.BorderFactory;
	import javax.swing.JButton;

	import acm.gui.IntField;
	import acm.gui.TableLayout;
	import acm.gui.TablePanel;
import acm.program.Program;


	public class Sudoku extends Program {
		
		// the model of the game board
		IntField[][] board;

		/**
		 * Construct a new game of Sudoku.
		 *
		 * Initializes the game board with all zeroes.
		 */
		public Sudoku() {
			super();
			board = new IntField[9][9];
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					board[i][j] = new IntField(0);
				}
			}
		}

		/**
		 * Initialize a new game of Sudoku with a given configuration.
		 *
		 * @param values
		 *            The configuration of the game board.
		 */
		public Sudoku(int[][] values) {
			this();
			setConfiguration(values);
		}

		/**
		 * Initialize the view component.
		 */
		@Override
		public void init() {
			setTitle("Sudoku");
			setLayout(new TableLayout(4, 3));
			for (int i = 0; i < 9; i++) {
				add(assembleInnerTable(i));
			}
			add(new JButton("Solve"));
			addActionListeners();
		}

		/**
		 * Assemble a single 3x3 field.
		 *
		 * @param n
		 *            The number of the 3x3 field to assemble a table component for.
		 * @return The TablePanel containing a 3x3 field.
		 */
		private TablePanel assembleInnerTable(int n) {
			TablePanel tp = new TablePanel(3, 3);
			for (int i = 0; i < 9; i++) {
				// we assemble 3x3 field-wise and have to adjust array indices
				// accordingly
				int row = 3 * (n / 3) + i / 3;
				int col = 3 * (n % 3) + i % 3;

				// The constructor made sure these are instantiated IntFields
				IntField intField = board[row][col];

				// Register a KeyListener to suppress non-digit entries
				intField.addKeyListener(new KeyListener() {
					@Override
					public void keyPressed(KeyEvent e) {
						// don't care
					}

					@Override
					public void keyReleased(KeyEvent e) {
						// don't care
					}

					@Override
					public void keyTyped(KeyEvent e) {
						try {
							// try to parse the pressed keys value into an Integer
							Integer.parseInt(String.valueOf(e.getKeyChar()));
						} catch (NumberFormatException nfe) {
							// consume the event and stop it from propagating
							e.consume();
						}
					}
				});
				tp.add(intField);
			}
			// draw a solid black border around every 3x3 field
			tp.setBorder(BorderFactory.createLineBorder(Color.black));
			return tp;
		}

		/**
		 * Initialize the game board with the given arrays of ints.
		 *
		 * @param init The 9x9 two-dimensional array with int values from 0..9
		 */
		public void setConfiguration(int[][] init) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					if (init[i][j] > 0 && init[i][j] <= 9) {
						board[i][j].setValue(init[i][j]);
					} else {
						board[i][j].setValue(0);
					}
				}
			}
		}

		/**
		 * Return the current configuration of the game board.
		 *
		 * @return The current configuration.
		 */
		public int[][] getConfiguration() {
			int[][] tmp = new int[9][9];
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					tmp[i][j] = board[i][j].getValue();
				}
			}
			return tmp;
		}

		// if no solution was found, color every field red
		public void colorForFailure() {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					board[i][j].setBackground(new Color(255, 0, 0));
				}
			}
		}

		// if there was a solution, color the new values fields green
		public void colorForSuccess(int[][] solution) {
			int[][] actual = getConfiguration();
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					if (solution[i][j] != actual[i][j]) {
						board[i][j].setBackground(new Color(100, 100, 200));
						board[i][j].setValue(solution[i][j]);
					} else {
						board[i][j].setBackground(new Color(50, 200, 50));
					}
				}
			}
		}

		/**
		 * The ActionListeners method to process pressed buttons.
		 */
		@Override
		public void actionPerformed(ActionEvent e) {
			if (e.getActionCommand().equals("Solve")) {
				// The solve button was pressed, find a solution
				int[][] solution = solve(getConfiguration());
				if (solution != null) {
					colorForSuccess(solution);
				} else {
					colorForFailure();
				}
			}
		}



		
		/**
		 * checks if the an array of 9 entries contains duplicates
		 * @param line
		 * the array, which has to be checked
		 * @return
		 * true if duplicates exist
		 * otherwise false
		 */
		private boolean checkForDuplicates(int[] line){
			for (int currPos=1; currPos<9; currPos++){
				if(line[currPos]!=0){
				for (int checkPos=0; checkPos<currPos; checkPos++){
					if (line[currPos]==line[checkPos])
						return true;
				}
				}
			}
			return false;
		}
		
		
		/**
		 * converts a row of a 9x9 table into a one dimensional int array
		 * @param row
		 * the number of row of the 9x9 table
		 * @param array
		 * the 9x9 table
		 * @return
		 * an int array with 9 entries
		 */
		private int[] rowToLine(int row, int[][] array){
			int[] line = new int[9];
			
			for (int col=0; col<9; col++){
				line[col]=array[row][col];
			}
			return line;
		}
		
		
		/**
		 * converts a column of a 9x9 table into a one dimensional int array
		 * @param col
		 * the number of column of the 9x9 table
		 * @param array
		 * the 9x9 table
		 * @return
		 * an int array with 9 entries
		 */
		private int[] colToLine(int col, int[][] array){
			int[] line = new int[9];
			
			for (int row=0; row<9; row++){
				line[row]=array[row][col];
			}
			return line;
		}
		
		
	/**
	 * converts a 3x3 block of the 9x9 table into an int array
	 * @param block
	 * the number of the used block the second in the first line is the second block
	 * @param array
	 * the 9x9 table
	 * @return
	 * an int array with 9 entries
	 */
		private int[] blockToLine(int block, int[][] array){
			int[] line = new int[9];
			int h = block / 3;
			int v = block % 3;
			int pos = 0; 
			
			for (int row=h*3; row<(h+1)*3; row++){
				for (int col=v*3; col<(v+1)*3; col++){
				line[pos]=array[row][col];
				pos++;
				}
			}
			return line;
		}
		
		
		
		/**
		 * checks an array for duplicates according to the rules of Sudoku
		 * 
		 * @param currArray 
		 * 		the array to be checked
		 * @return
		 *   	true if there are duplicates
		 *      false if not
		 */
		public boolean reject(int[][] currArray){
            //if(currArray==null) return true;

      
           for (int i=0; i<9; i++){
        	   if (checkForDuplicates(rowToLine(i, currArray)) ||
        		   checkForDuplicates(colToLine(i, currArray)) ||
        		   checkForDuplicates(blockToLine(i, currArray)))
        		   return true;
           }
           return false;
           
		}
            
            
            
     
		
		
		
		/**
		 * returns the position of the next free (value 0) field  of an array
		 * 
		 * @param currArray 
		 *    the array 
		 * @return
		 *    a position from 0 to 80, or -1 if there is no free field
		 */
		int getNextFreeField(int[][] currArray){
			for (int row=0; row<9; row++){
				for (int col=0; col<9; col++){
					if (currArray[row][col]==0) 
						return 9*row+col;	
				}}
			return -1;
		}

		
		/**
		 * adds 1 to the value of a given field if it is below 9
		 * 
		 * @param currArray
		 * 		the array containing the field
		 * @param position
		 * 		the position of the field
		 * @return
		 * 		the changed array or null if the position was invalid
		 */
		
		int[][] getNextExtension(int[][] currArray, int position){
			//invalid position
			if (position<0||position>80) return null;
			
			
		    int[][] newField = new int[9][9];
		    for (int i=0; i<9; i++)
		    	for(int j=0;j<9;j++)
		   		newField[i][j]=currArray[i][j];  
		    

			int row = position / 9;
			int col = position % 9;
			if (newField[row][col]<9) { 
				    newField[row][col]++;
				    return newField;}
			else
				// invalid value
				return null; 
			}
			
		
		/**
		 * finds a solution for a given Sudoku
		 * 
		 * @param toSolve  
		 * 		the Sudoku to be solved
		 * @param position
		 * 		the first field which is to be changed 
		 * @return
		 *  	a completely filled and correct Sudoku
		 */

		int[][] solve(int[][] toSolve, int position){
			int[][] newField = getNextExtension(toSolve, position);
			
			boolean reject = reject(toSolve);
			int nextField = getNextFreeField(toSolve);
	
			if (reject==true){
	           	//invalid position
	           	if (newField==null)
	           		return null;
	           //no valid number at position	
	           return solve(newField, position);	
			  }
			else{
				//solution found
				if(nextField == -1)
					return toSolve; 
				//int at position is 9
	           	if (newField==null)
	           		return solve(toSolve, nextField);
				//0 at position
				if(nextField==position)
					return solve(newField, position);

				int[][] nextTry = solve(toSolve, nextField);          	
				//continue searching
				if (nextTry == null){
					return solve(newField, position);
				}
				else{
					return nextTry;
				}
			}
           	

           		
		}
		
		/**
		 * Solve the given Sudoku configuration and return the result.
		 *
		 * @param configuration A 9x9 two-dimensional array, (columns?) rows first.
		 * @return The solution for this game of Sudoku.
		 */
		public  int[][] solve(int[][] configuration) {
            return solve(configuration, getNextFreeField(configuration));
     
		}

		public static void main(final String[] args) {
			final int[][] emptyField = new int[][] { { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
					{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
					{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
					{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
					{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 } };

			final int[][] fullField = new int[][] { { 5, 3, 4, 6, 7, 8, 9, 1, 2 },
					{ 6, 7, 2, 1, 9, 5, 3, 4, 8 }, { 1, 9, 8, 3, 4, 2, 5, 6, 7 },
					{ 8, 5, 9, 7, 6, 1, 4, 2, 3 }, { 4, 2, 6, 8, 5, 3, 7, 9, 1 },
					{ 7, 1, 3, 9, 2, 4, 8, 5, 6 }, { 9, 6, 1, 5, 3, 7, 2, 8, 4 },
					{ 2, 8, 7, 4, 1, 9, 6, 3, 5 }, { 3, 4, 5, 2, 8, 6, 1, 7, 9 } };

			final int[][] actualField1 = new int[][] {
					{ 5, 3, 0, 0, 7, 0, 0, 0, 0 }, { 6, 0, 0, 1, 9, 5, 0, 0, 0 },
					{ 0, 9, 8, 0, 0, 0, 0, 6, 0 }, { 8, 0, 0, 0, 6, 0, 0, 0, 3 },
					{ 4, 0, 0, 8, 0, 3, 0, 0, 1 }, { 7, 0, 0, 0, 2, 0, 0, 0, 6 },
					{ 0, 6, 0, 0, 0, 0, 2, 8, 0 }, { 0, 0, 0, 4, 1, 9, 0, 0, 5 },
					{ 0, 0, 0, 0, 8, 0, 0, 7, 9 } };

			final int[][] actualField2 = new int[][] {
					{ 1, 0, 2, 0, 0, 0, 0, 0, 0 }, { 0, 0, 3, 0, 0, 0, 0, 0, 0 },
					{ 0, 0, 0, 0, 0, 0, 0, 0, 4 }, { 0, 4, 0, 0, 5, 0, 0, 0, 0 },
					{ 0, 6, 0, 0, 7, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 2, 0 },
					{ 0, 8, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
					{ 0, 0, 0, 0, 0, 0, 8, 0, 0 } };

			
			final int[][] fullField2 = new int[][] { { 0, 0, 0, 6, 7, 8, 9, 1, 2 },
					{ 6, 7, 2, 1, 9, 5, 3, 4, 8 }, { 1, 0, 8, 3, 4, 2, 5, 6, 7 },
					{ 8, 5, 9, 7, 6, 1, 4, 2, 3 }, { 0, 2, 6, 8, 5, 3, 7, 9, 1 },
					{ 7, 1, 3, 9, 2, 4, 8, 5, 6 }, { 9, 6, 1, 5, 3, 7, 2, 8, 4 },
					{ 2, 8, 7, 4, 1, 9, 6, 3, 5 }, { 3, 4, 5, 2, 8, 6, 1, 7, 9 } };
			
			
			
			Sudoku a=new Sudoku();
		    new Sudoku(emptyField).start();
			
            //System.out.println(a.solve(actualField2));
            
			
		}

	}

